1. Field
Example embodiments are related to methods for restructuring a program, and for example, to methods for restructuring a program using context-free grammar transformations.
2. Background
A personal computer's operating system contains many megabytes of programs that may contain unpublicized, exploitable vulnerabilities. Application programs multiply a size of an exposed code base, and current forms of mobile code now supported by many operating systems and browsers open the vulnerabilities to a wider range of attacks for network-connected systems. As organizations move more and more toward software monocultures where a majority of hosts share some common software identical in both version and patch level the above problems become worse.
Conventional defense strategies include vulnerability scanners, network security bundles (e.g., with firewalls, virus scans, spam blockers, and privacy controls), intrusion detection and intrusion prevention systems, identity management systems, and insider threat management systems. However, effective attacks are still mounted against computer systems employing conventional defense strategies, and security patches are commonplace.
An attack that is successful against one version of a particular program will be successful against all instances of the program having the same version. Recent research has focused on diversity as a method to protect individual hosts and guard against large-scale attacks. Instruction set randomization (ISR) is used within software dynamic translation systems to provide process-specific instruction sets to protect against code injection attacks. N-variant systems, if supplied with program variants with disjoint vulnerabilities, observe the difference in program behavior to detect attacks. Address randomization techniques guard against memory error attacks by randomizing the location of segments (i.e., stack, heap, and code) within process memory space, and by randomizing the order and spacing of stack and heap variables within the segments.
Software diversity has been shown to be a viable method of software defense. Research suggests that the greater the degree of diversity the more effective the defense. Instruction set randomization (ISR) and address randomization techniques automatically create numerous diverse programs. However, all of the instances of a given program have the same code structure, i.e., all the instances of a given program have the same set of functions, and the functions have the same parameters and the same set of stack and heap variables. Instruction set randomization (ISR) depends on a secret key which may be systematically guessed, and address randomization techniques only randomize variable ordering without randomizing a structure of a program.